/*
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。
*/
class Solution {

/*
故渐进时间复杂度为 (kn×logk)。
空间复杂度：递归会使用到 O(logk) 空间代价的栈空间。
*/
    public ListNode mergeKLists(ListNode[] lists) {
       return merge(lists,0,lists.length -1);
    }
    

    public ListNode merge(ListNode[] lists,int left,int right) {
        if(left==right){
            return lists[left];
        }
        if(left > right){
            return null;
        }
        int mid = left+(right - left)/2;
        return mergeTwoLists(merge(lists,left,mid),merge(lists,mid+1,right));
    }

    public ListNode mergeKListsSmple(ListNode[] lists) {
        ListNode res = null;
        for(int i=0; i< lists.length;i++){
            res = mergeTwoLists(res,lists[i]);
        }
        return res;
    }
    

 

    public ListNode mergeTwoLists(ListNode l1,ListNode l2) {
        if(l1==null||l2==null){
            return l1==null?l2:l1;
        }
        ListNode dummyNode = new ListNode(-1);
        ListNode curr = dummyNode;//l1=la,l2=lb;
        while(l1!=null && l2!=null){
            if(l1.val<=l2.val){
                curr.next=l1;
                l1=l1.next;
            }else{
                curr.next=l2;
                l2=l2.next;
            }
            curr=curr.next;
        }
        curr.next = l1==null?l2:l1;
        return dummyNode.next;
    }
}